This section will extend the idea of the tiling systems to an approach which is using Wang tiles instead of usual tiles. A Wang tile is a unit square with colored edges (see figure~\ref{figure:wang_tile}). 

\begin{figure}[ht]
	\begin{center}
		\includegraphics[scale=0.5]{img/single-wang-tile.png}
		\caption{A Wang tile}
		\label{figure:wang_tile}
	\end{center}
\end{figure}

If we have an image of size $(m, n)$ of Wang tiles, we speak of a \emph{valid tiling}, when for $1 \leq i < m$ and $1 \leq j < n$, the right color of the tile at position $(i - 1, j)$ is equal to the left color of the tile at position $(i, j)$ and the color at the bottom of the tile at position $(i, j - 1)$ is equal to the top color of the tile at position $(i, j)$. 

If we extend each tile by a label, we are able to generate pictures out of the labels from valid tilings. This idea can be used for a formal definition described in~\cite{lonati2011towards}:

\begin{definition}
	A quintuple $A = (a, t, l, r, b) \in \Sigma\times C^4$ is called a \emph{labelled Wang tile} where 	
	\begin{compactitem}
		\item $\Sigma$ is a finite alphabet,
		\item $C$ is a finite set of colors including the border color \#,
		\item a is the label of the Wang tile and
		\item t, l, r, b are representing the colors at top, left, right and bottom of the Wang tile.
	\end{compactitem}
\end{definition}

Despite the representation as a quintuple, we will also use the following notion for better readability: 
\(A = 
\begin{tabular}{m{0.1cm}m{0.2cm}m{0.2cm}}
	& t &   \\[-0.5ex]
	\cline{2-2}
	l & \multicolumn{1}{|c|}{a} & r \\[-0.2ex]
	\cline{2-2}
	& b & 
\end{tabular}\). The set of labelled Wang tiles with labels in $\Sigma$ and colors in $C$ is denoted as $\Sigma_{4C}$. For a Wang tile $A$, we denote the color of the edge towards right, left, top and bottom with $A_d$ for $d \in \{\leftarrow, \rightarrow, \uparrow, \downarrow\}$. The domain of a labelled Wang tile $\Delta_A$ is the set of colors used by the labelled Wang tile $A$ and $\Sigma_C$ describes the set of partial tiles, whereby a partial tile is a Wang tile with some undefined colors. 

\begin{definition}
	Let $\Sigma$ be a finite alphabet and $C$ be a finite set of colors. A picture $p \in \Sigma_{4C}^{*,*}$ is called a \emph{Wang picture}, if the following conditions are satisfied:
	
	\begin{compactitem}
		\item The borders of the picture are colored with \#'s and every non-border is not colored by \#'s, 
		\item $p(i,j)_\rightarrow = p(i + 1, j)_\leftarrow$ for every $1 \leq i < l_2(p)$ and
  \item $p(i,j)_\downarrow = p(i, j + 1)_\uparrow$ for every $1 \leq j < l_1(p)$. 
	\end{compactitem}
\end{definition}

This definition coincides with the description of valid tilings and furthermore requires that the picture is bordered. The label of a Wang picture is the picture which consists only of the labels of the Wang tiles.

In the following, we will use one of the following representations: 

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
wang picture & label & short form \\
\hline
\(
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|c|c|}
\hline
		\begin{tabular}{rcl}
		   	& \#        &   \\[-0.5ex]
		   	\cline{2-2}
			\# & \multicolumn{1}{|c|}{a} & 4 \\[-0.2ex]
			\cline{2-2}
		   	& 1         & 
		\end{tabular}  			 	&		\begin{tabular}{rcl}
											  	& \#         &    \\[-0.5ex]
											  	\cline{2-2}
											  	4 & \multicolumn{1}{|c|}{b}  & \# \\[-0.2ex]
												\cline{2-2}
											  	& 3          & 
											\end{tabular} 				\\		
\hline
		\begin{tabular}{rcl}
		   & 1         &   \\[-0.5ex]
		   \cline{2-2}
		\# & \multicolumn{1}{|c|}{b} & 2 \\[-0.2ex]
			\cline{2-2}
		   & \#        & 
		\end{tabular} 				&	 	\begin{tabular}{rcl}
											  & 3         &    \\[-0.5ex]
											  \cline{2-2}
											2 & \multicolumn{1}{|c|}{a} & \# \\[-0.2ex]
											\cline{2-2}
											  & \#        & 
											\end{tabular}				\\
\hline
\end{tabular}
\setlength{\tabcolsep}{6pt}
\)
& 
\(
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|c|c|}
\hline
		a  			 	&		b 				\\		
\hline
		b 				&	 	a				\\
\hline
\end{tabular} \) 
\setlength{\tabcolsep}{6pt}
&
\( 
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|rcccl|}
\hline
   & \#        &   & \#        &    \\[-0.5ex]
   \cline{2-2}\cline{4-4}
\# & \multicolumn{1}{|c|}{a} & 4 & \multicolumn{1}{|c|}{b} & \# \\[-0.2ex]
   \cline{2-2}\cline{4-4}
   & 1         &   & 3         &    \\[-0.5ex]
      \cline{2-2}\cline{4-4}
\# & \multicolumn{1}{|c|}{b} & 2 & \multicolumn{1}{|c|}{a} & \# \\[-0.2ex]
   \cline{2-2}\cline{4-4}
   & \#        &   & \#        &    \\
\hline
\end{tabular}
\setlength{\tabcolsep}{6pt}
\)  \\
\hline
\end{tabular}
\end{center}

With the previous definitions we are now able to introduce the system which can generate two-dimensional languages using Wang tiles and Wang pictures. 

\begin{definition}
	Let $C$ be a finite set of colors, $\Sigma$ is a finite set of labels and $\Theta \subseteq \Sigma_{4C}$ is a finite set of Wang tiles. 
	
	The triple $\omega = (C, \Sigma, \Theta)$ is called \emph{Wang system} (WS). 
\end{definition}

The language generated by a Wang system $L(\omega)$ is the set of labels representing a valid tiling using the Wang tiles of the Wang system. If a language can be generated using a Wang system, the language is called \emph{Wang recognizable}. 

\begin{example}
	Let $\omega = (C, \Sigma, \Theta)$ be a Wang system with $C = \{c_a, c_b, -\}$, $\Sigma = \{a, b\}$ and 
	\begin{align*} \Theta = \left\lbrace
\begin{tabular}{c}
\begin{tabular}{rcl}
 & \# & \\[-0.5ex]
\# & \boxed{x} & - \\[-0.2ex]
 & $c_x$ & 
\end{tabular}, 
\begin{tabular}{rcl}
 & \# & \\[-0.5ex]
- & \boxed{x} & - \\[-0.2ex]
 & $c_x$ & 
\end{tabular}, 
\begin{tabular}{rcl}
 & \# & \\[-0.5ex]
- & \boxed{x} & \# \\[-0.2ex]
 & $c_x$ & 
\end{tabular}, 
\begin{tabular}{rcl}
 & \# & \\[-0.5ex]
\# & \boxed{x} & \# \\[-0.2ex]
 & $c_x$ & 
\end{tabular},\\[1ex]
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
\# & \boxed{y} & - \\[-0.2ex]
 & $c_x$ & 
\end{tabular}, 
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
- & \boxed{y} & - \\[-0.2ex]
 & $c_x$ & 
\end{tabular}, 
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
- & \boxed{y} & \# \\[-0.2ex]
 & $c_x$ & 
\end{tabular}, 
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
\# & \boxed{y} & \# \\[-0.2ex]
 & $c_x$ & 
\end{tabular},\\[1ex]
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
\# & \boxed{x} & - \\[-0.2ex]
 & \# & 
\end{tabular}, 
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
- & \boxed{x} & - \\[-0.2ex]
 & \# & 
\end{tabular}, 
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
- & \boxed{x} & \# \\[-0.2ex]
 & \# & 
\end{tabular}, 
\begin{tabular}{rcl}
 & $c_x$ & \\[-0.5ex]
\# & \boxed{x} & \# \\[-0.2ex]
 & \# & 
\end{tabular}
\end{tabular}
\right\rbrace
\end{align*}

be the set of tiles, for $x, y \in \{a, b\}$. 

The language $L(\omega) = \{p \in \{a, b\}^{*,*} \mid p(1, i) = p(l_1(p), i) \text{ for } 1 \leq i \leq l_2(p)\}$ contains pictures over $\{a, b\}$ where the first and the last row are identical. 
\end{example}

This can be achieved because the Wang tiles have the possibility to store the label of the first element in the column in the downward colors. Any Wang tile except the bottom ones can have any label, but contains the label of the first row as color. An example Wang picture of $L(\omega)$ is the following: 

\begin{center}
\begin{tabular}{rcl}
\begin{tabular}{rcccccccl}
   & \# & & \# & & \# & & \# & \\
\# & \boxed{a} & - & \boxed{a} & - & \boxed{b} & - & \boxed{b} & \#\\
 & $c_a$ &  & $c_a$ &  & $c_b$ &  & $c_b$ & \\
 \# & \boxed{b} & - & \boxed{a} & - & \boxed{b} & - & \boxed{a} & \#\\
 & $c_a$ &  & $c_a$ &  & $c_b$ &  & $c_b$ & \\
 \# & \boxed{a} & - & \boxed{b} & - & \boxed{b} & - & \boxed{b} & \#\\
 & $c_a$ &  & $c_a$ &  & $c_b$ &  & $c_b$ & \\
 \# & \boxed{a} & - & \boxed{a} & - & \boxed{b} & - & \boxed{b} & \#\\
   & \# & & \# & & \# & & \# & 
\end{tabular}
&
$\leadsto$
&
\boxed{\begin{tabular}{rccl}
a & a & b & b\\
b & a & b & a\\
a & b & b & b\\
a & a & b & b
\end{tabular}}
\end{tabular}
\end{center}

\begin{theorem}
	The class of languages that are Wang recognizable is the class REC~\cite{cherubini2009picture}. 
\end{theorem}

This last theorem shows that even if this class of languages is using a different approach of tiling, the class of languages that can be generated is the same class of pictures recognized by tiling systems. 

In the next section we will see another approach of determinism in tiling systems using Wang tiles. 